package 力扣热题100;

public class LeetCode14 {
    /**
     * 方法一，顺序合并多个数组
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {

        ListNode Node=null;
        for (int i = 0; i < lists.length; i++) {
            Node= mergeTwoLists(Node,lists[i]);
        }
        return Node;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null){
            return null;
        }
        ListNode listNode=new ListNode(0);
        ListNode head=listNode;
        while (list1!=null&&list2!=null){
            while (list1!=null&&list2!=null&&list1.val<=list2.val){
                listNode.next=list1;
                listNode=listNode.next;
                list1=list1.next;
            }
            while (list1!=null&&list2!=null&&list2.val<=list1.val){
                listNode.next=list2;
                listNode=listNode.next;
                list2=list2.next;
            }
        }
        if(list1==null){
            listNode.next=list2;
        }else {
            listNode.next=list1;
        }
        return head.next;
    }
    /**
     * 方法二，归并排序
     */
    public ListNode mergeKLists(ListNode[] lists){
        return apart(lists,0,lists.length-1);
    }

    private ListNode apart(ListNode[] lists, int l, int r) {//分
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid=(l+r)/2;
        return merge(apart(lists,l,mid),apart(lists,mid+1,r));
    }

    private ListNode merge(ListNode apart1, ListNode apart2) {//合并
        if(apart1==null||apart2==null){
            return apart1!=null?apart1:apart2;
        }
        ListNode listNode=new ListNode(0);
        ListNode a=apart1,b=apart2,head=listNode;
        while (a!=null&&b!=null){
            if(a.val>b.val){
                listNode.next=b;
                b=b.next;
            }else {
                listNode.next=a;
                a=a.next;
            }
            listNode=listNode.next;
        }
        listNode.next=a!=null?a:b;
        return head.next;
    }

}
